О ЧИСЛЕ ЭЛЕМЕНТОВ СХЕМЫ, РЕАЛИЗУЮЩЕЙ ОБОБЩЕННУЮ ФУНКЦИЮ ГОЛОСОВАНИЯ 

Алехина Марина Анатольевна, доктор физико-математических наук, профессор, заведующая кафедрой дискретной математики, Пензенский государственный университет (г. Пенза, ул. Красная, 40), alehina@pnzgu.ru 

519.718 

Рассматривается один из важнейших разделов математической кибернетики – теория синтеза, надежности и сложности управляющих систем. Актуальность исследований в этой области обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники. Все разнообразные средства цифровой техники: ЭВМ, микропроцессорные системы измерений и автоматизации технологических процессов, цифровая связь, телевидение и т.д., строятся на единой элементной базе, в состав которой входят чрезвычайно разные по сложности микросхемы – от логических элементов, выполняющих простейшие операции, до сложнейших программируемых кристаллов, содержащих миллионы логических элементов. Логические элементы цифровых устройств во многом определяют функциональные возможности последних, их конструктивное исполнение, технологичность, надежность. К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из
ненадежных функциональных элементов, реализующие булевы функции. В ряде результатов, относящихся к реализации булевых функций надежными схемами из ненадежных функциональных элементов, фигурирует параметр Ngˆ – наименьшее число функциональных элементов, необходимых для реализации функции голосования x` в рассматриваемом полном базисе. Оказалось, что еще и другие функции (обозначим их множество через G) обладают свойствами, аналогичными свойствам функции голосования. Эти функции имеют вид 1 2 1 3 2 3 x1 x2 x1 x3 x2 x3 σ σ ∨ σ σ ∨ σ σ ( {0,1} σi ∈ , i∈{1,2,3}) и в статье называются обобщенными функциями голосования, т.е. G – множество функций вида 1 2 1 3 2 3 x1 x2 x1 x3 x2 x3 σ σ ∨ σ σ ∨ σ σ . Пусть Ng – наименьшее число абсолютно надежных функциональных элементов, необходимых для реализации функции g ∈ G в рассматриваемом полном базисе, а G min g g G N N ∈= , т.е. NG – наименьшее число абсолютно надежных функциональных элементов, достаточное для реализации хотя бы одной функции из множества G в рассматриваемом полном базисе. Цель данной работы – получить верхнюю оценку величины NG, которая была бы справедлива в произвольном полном базисе. Предполагается, что все функциональные элементы базиса абсолютно надежны. Для получения верхней оценки величины NG использованы те же методы и подходы, что и при доказательстве известной теоремы Поста о полноте систем булевых функций. Доказано, что в произвольном полном конечном базисе хотя бы одну функцию множества G можно реализовать схемой, содержащей не более восьми функциональных элементов. Используя это свойство, можно в неравенствах заменить величину NG константой 8. В ранее известных результатах по надежности схем, состоящих из ненадежных функциональных элементов и содержащих величину NG – зависящую от рассматриваемого базиса, можно улучшить ряд Известия высших учебных заведений. Поволжский регион 6 University proceedings. Volga region ранее известных оценок ненадежности асимптотически оптимальных по надежности схем.

функциональные элементы, синтез схем из функциональных элементов. 

1. Яблонский, С. В. Введение в дискретную математику / С. В. Яблонский. – М. : Высш. шк.,2001.–384 с.
2. Лу панов, О. Б. Асимптотические оценки сложности управляющих систем / О. Б. Лупанов. – М. : Изд-во МГУ, 1984. – 138 с.
3. Алехина, М. А. О числе элементов схемы, реализующей функцию голосования / М. А. Алехина, С. Ю. Епифанов // Молодежная математическая наука – 2012 : сб. материалов Всероссийской с Междунар. участием молодежной научно-практической конф. (Саранск, 27–28 апреля 2012 г.). – Саранск : Изд-во Мордовского гос. пед. института имени М. Е. Евсевьева, 2012. – С. 94–96.
4. Аксенов, С. И. О надежности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов / С. И. Аксенов // Известия высших учебных заведений. Поволжский регион. Естественные науки. – 2005. – № 6 (21). – С. 42–55.
5. Алехина, М. А. О надежности схем в произвольном полном конечном базисе при однотипных константантных неисправностях на выходах элементов / М. А. Алехина // Дискретная математика. – 2012. – Т. 24, № 3. – С. 17−24.
6. Алехина, М. А. Об одном свойстве немонотонных булевых функций / М. А. Алехина // Проблемы автоматизации и управления в технических системах – 2011 : тр. Междунар. науч.-техн. конф. (г. Пенза, 19–22 апреля 2011 г.) – Пенза : Изд-во ПГУ, 2011. – 1 т. – С. 91–93.
7. Редькин, Н. П. О полных проверяющих тестах / Н. П. Редькин // Математические вопросы кибернетики : сб. ст. / под ред. С. В. Яблонского. – Вып. 2. – М. : Наука, 1989. – С. 198–222.